---
title: "6、岛屿个数"
created: 2025-11-28
tags:
  - 算法
---

# 6、岛屿个数

## 题目 [岛屿个数](https://www.lanqiao.cn/paper/3818/problem/3513/)

![[image-ddc8c2fc.png]]

## 思路分析

先染色法 把外海标记出来

再用洪水灌溉 找岛屿数 如果岛屿能连接到外海 就是岛屿计数++ 如果连不到外海 就说明是岛中岛 不计数

结合了填涂颜色 山峰山谷几道题…蓝桥杯这样玩呢

![[image-46946d41.png]]

这题确实不错 写得出说明前面染色法和洪水填充都学会了

找陆地部分bfs dfs都可以实现

和历届的一道全球变暖也有点像 升级版

## 代码实现

```cpp
#include<bits/stdc++.h>

using namespace std;

#define endl '\n'

typedef pair<int,int> PII;

const int N=55;

int g[N][N];

bool st[N][N];

int n,m;

bool isVaild(int x,int y){

	return x>=0 && x<=n+1 && y>=0 && y<=m+1;

}

//八连通找外海

int dx_h[8]={-1,-1,0,1,1,1,0,-1};

int dy_h[8]={0,1,1,1,0,-1,-1,-1};

void bfs(int x,int y){

	queue<PII> q;

	q.push({x,y});

	st[x][y]=true;

	while(q.size()){

		auto cur=q.front();q.pop();

		int ux=cur.first,uy=cur.second;

		g[ux][uy]=2;

		for(int i=0;i<8;i++){

			int nx=ux+dx_h[i],ny=uy+dy_h[i];

			if(isVaild(nx,ny) && g[nx][ny]==0 && !st[nx][ny]){

				st[nx][ny]=true;

				q.push({nx,ny});

			}

		}

	}

}

//四连通找陆地

int dx_l[4]={-1,0,1,0};

int dy_l[4]={0,1,0,-1};

void dfs(int x,int y,bool &island){

	for(int i=0;i<4;i++){

		int nx=x+dx_l[i],ny=y+dy_l[i];

		if(isVaild(nx,ny)){

			if(g[nx][ny]==2){

				island=true;

			}

			if(g[nx][ny]==1 && !st[nx][ny]){

				st[nx][ny]=true;

				dfs(nx,ny,island);

			}

		}

	}

}

int main()

{

	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

	int T;

	cin>>T;

	while(T--){

		cin>>n>>m;

		memset(g,0,sizeof g);

		memset(st,false,sizeof st);

		for(int i=1;i<=n;i++){

			string s;cin>>s;

			for(int j=1;j<=m;j++){

				g[i][j]=s[j-1]-'0';

			}

		}//数据在1~n 1~m 外圈加了一圈0 范围0~n+1 0~m+1

//		for(int i=0;i<=n+1;i++){

//			for(int j=0;j<=m+1;j++){

//				cout<<g[i][j]<<" ";

//			}

//			cout<<endl;

//		}

		bfs(0,0);//染色法 标记外海

//		for(int i=0;i<=n+1;i++){

//			for(int j=0;j<=m+1;j++){

//				cout<<g[i][j]<<" ";

//			}

//			cout<<endl;

//		}

		//洪水灌溉找连通块 且有外海相邻

		int cnt=0;

		for(int i=1;i<=n;i++){

			for(int j=1;j<=m;j++){

				if(g[i][j]==1 && !st[i][j]){

					bool island=false;

					st[i][j]=true;

					dfs(i,j,island);

					if(island){

						cnt++;

					}

				}

			}

		}

		cout<<cnt<<endl;

	}

	return 0;

 }
```

```cpp
#include<bits/stdc++.h>

using namespace std;

#define endl '\n'

typedef pair<int,int> PII;

const int N=55;

int g[N][N];

bool st[N][N];

int n,m;

bool isVaild(int x,int y){

	return x>=0 && x<=n+1 && y>=0 && y<=m+1;

}

int dx_h[8]={-1,-1,0,1,1,1,0,-1};

int dy_h[8]={0,1,1,1,0,-1,-1,-1};

void bfs1(int x,int y){

	queue<PII> q;

	q.push({x,y});

	st[x][y]=true;

	while(q.size()){

		auto cur=q.front();q.pop();

		int ux=cur.first,uy=cur.second;

		g[ux][uy]=2;

		for(int i=0;i<8;i++){

			int nx=ux+dx_h[i],ny=uy+dy_h[i];

			if(isVaild(nx,ny) && g[nx][ny]==0 && !st[nx][ny]){

				st[nx][ny]=true;

				q.push({nx,ny});

			}

		}

	}

}

int dx_l[4]={-1,0,1,0};

int dy_l[4]={0,1,0,-1};

void bfs2(int x,int y,bool &island){

	queue<PII> q;

	q.push({x,y});

	st[x][y]=true;

	while(!q.empty()){

		auto cur=q.front();q.pop();

		int ux=cur.first,uy=cur.second;

		for(int i=0;i<4;i++){

			int nx=ux+dx_l[i],ny=uy+dy_l[i];

			if(isVaild(nx,ny)){

				if(g[nx][ny]==2){

					island=true;

				}

				if(g[nx][ny]==1 && !st[nx][ny]){

					st[nx][ny]=true;

					q.push({nx,ny});

				}

			}

		}

	}

}

int main()

{

	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

	int T;

	cin>>T;

	while(T--){

		cin>>n>>m;

		memset(g,0,sizeof g);

		memset(st,false,sizeof st);

		for(int i=1;i<=n;i++){

			string s;cin>>s;

			for(int j=1;j<=m;j++){

				g[i][j]=s[j-1]-'0';

			}

		}//数据在1~n 1~m 外圈加了一圈0 范围0~n+1 0~m+1

//		for(int i=0;i<=n+1;i++){

//			for(int j=0;j<=m+1;j++){

//				cout<<g[i][j]<<" ";

//			}

//			cout<<endl;

//		}

		bfs1(0,0);//染色法 标记外海 为2

//		for(int i=0;i<=n+1;i++){

//			for(int j=0;j<=m+1;j++){

//				cout<<g[i][j]<<" ";

//			}

//			cout<<endl;

//		}

		//洪水灌溉找连通块 且有外海相邻

		int cnt=0;

		for(int i=1;i<=n;i++){

			for(int j=1;j<=m;j++){

				if(g[i][j]==1 && !st[i][j]){

					bool island=false;

					bfs2(i,j,island);

					if(island){

						cnt++;

					}

				}

			}

		}

		cout<<cnt<<endl;

	}

	return 0;

 }
```

## 同类题型

## 视频讲解

---
⬅️ [[5、接龙序列|5、接龙序列]] 🏠 [[00-刷题理模型]] ➡️ [[7、子串简写|7、子串简写]]